package EveryDay;

import java.util.PriorityQueue;
import java.util.Queue;
/**
 * p871 最低加油次数
 * */
public class P871 {
    public static void main(String[] args) {
        int a=100;
        int b=10;
        int[][] nums={{10,60}, {20, 30}, {30, 30}, {60, 40}};
        P871Test02 p871Test02=new P871Test02();

        System.out.println(p871Test02.minRefuelStops(a, b, nums));
    }
}
/**
 * 解法：动态规划 01背包（13个样例）
 * */
class P871Test01{
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        //如果能直接到达就返回0
        if(startFuel>=target)
            return 0;
        if(stations.length==0&&target>startFuel)
            return -1;


        //第一个加油站到不了
        if(startFuel<stations[0][0])
            return -1;

        int[] f=new int[target+1];

        for(int i=0;i<stations.length;i++){
            for(int j=target;j>=0;j--){
                if(j>stations[i][1])
                    f[j]=Math.max(f[j],f[j-stations[i][1]]+1);
            }
        }

        return f[target];

    }
}

/**
 * 如果油够就一直跑，不够的话就取出之前跑过的油来加
 * */
class P871Test02{
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        //特判
        if(stations.length==0)
            return startFuel>=target?0:-1;
        //用来存储油的优先队列（堆），如果能到达加油站就放到后备箱，不能的话直接加油
        Queue<Integer> queue=new PriorityQueue<>((o1, o2) -> o2-o1);
        int  length=stations.length;
        //用来记录油
        int fuel=startFuel;
        //答案
        int ans=0;

        for(int i=0;i<length;i++){
            //油不够开到下一个加油站
            while(fuel<stations[i][0])
            {
                //取出来加油
                Integer temp=queue.poll();
                //如果取不出来就返回-1
                if(temp==null) return -1;
                //能够取出来的话就加到fuel里面
                fuel+=temp;
                //次数加1
                ans++;
            }
            //如果够用的话就放到后备箱
            queue.add(stations[i][1]);
        }

        //如果这样走到后面,发现还是到不了加油站的话就取出后备箱的油继续加
        while(fuel<target){
            //取出来加油
            Integer temp=queue.poll();
            //如果取不出来就返回-1
            if(temp==null) return -1;
            //能够取出来的话就加到fuel里面
            fuel+=temp;
            //次数加1
            ans++;
        }

        return ans;

    }
}
